package com.learn.algorithm_1_march;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 快速排序
 */
public class QuickSortTest {
    @Test
    public void test() {
        int[] array = {27, 34, 25, 12, 22, 11, 90};
        quickSort(array, 0, array.length - 1);
        // print
        List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
        System.out.println(list);
    }

    /**
     *
     * @param array 原始数组
     * @param low 起始点
     * @param high 终止点
     */
    private void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivot = partition(array, low, high);
            // pivot位置不用参与排序
            quickSort(array, low, pivot-1);
            quickSort(array, pivot+1, high);
        }
    }

    private int partition(int[] array, int low, int high) {
        int start = array[low];
        // 左指针
        int i = low + 1;
        // 右指针
        int j = high;

        while (i <= j) {
            System.out.println("i,j: " + i + "," + j);
            if (start > array[i]) {
                i++;
            }
            else if (start < array[j]) {
                j--;
            }
            else {
                int val = array[i];
                array[i] = array[j];
                array[j] = val;
            }
        }
        // 此时i > j, 并且以array[j]为分割线，根据大于小于start分成了两部份，
        // 替换array[j] 和 start的值
        int Jval = array[j];
        array[j] = array[low];
        array[low] = Jval;

        return j;
    }

}
